package other;

public class StringMatch {
    public static void main(String[] args) {
        int result = kmpMatch("你好不吗你好吗你不好 吗你不好吗","你不好吗");
        //int result = kmpMatch("ABCDABCDABDABCDACD","ABCDABD");
        System.out.println(result);
    }
    public static int forceMatch(String str1,String str2){
        char[] ac1 = str1.toCharArray();
        char[] ac2 = str2.toCharArray();
        int j;
        int index;
        for (int i=0;i<ac1.length;i++){
            index = i;
            for(j=0;j<ac2.length;j++){
                if(ac1[index++]!=ac2[j]){
                    break;
                }
            }
            if(j==ac2.length){
                return i;
            }
        }

        return -1;
    }

    public static int forceMatch2(String str1,String str2){
        char[] ac1 = str1.toCharArray();
        char[] ac2 = str2.toCharArray();
        int j = 0;
        int i = 0;
        while(i<ac1.length&&j<ac2.length){
            if(ac1[i]==ac2[j]){
                j++;
                i++;
            }else{
                i=i-(j-1);
                j=0;
            }
        }
        if(j==ac2.length){
            return i-j;
        }
        return -1;
    }
    public static int kmpMatch(String str1,String str2){
        int j=0;
        int i=0;
        int[] next = kmpNext(str2);
        while(i<str1.length()&&j<str2.length()){
            //如果字符不同就把后缀当前缀进行比对
            while(j>0&&str1.charAt(i)!=str2.charAt(j)){
                j = next[j-1];
            }
            if(str1.charAt(i)==str2.charAt(j)){
                j++;
            }
            i++;
        }
        if(j==str2.length()){
            return i-j;
        }
        return -1;
    }
    public static int[] kmpNext(String dest){
        int[] next = new int[dest.length()];
        next[0] = 0;
        for(int i=1,j=0;i<dest.length();i++){
            while(j>0&&dest.charAt(i)!=dest.charAt(j)){
                j = next[j-1];
            }
            if(dest.charAt(i)==dest.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
